/**
 * 
 */
package dp.passed;

/**
 * @author xyyi
 *
 */
public class InterleavingString {

	/**
	Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.

	For example,
	Given:
	s1 = "aabcc",
	s2 = "dbbca",

	When s3 = "aadbbcbcac", return true.
	When s3 = "aadbbbaccc", return false.
	 */
	public boolean isInterleave(String s1, String s2, String s3) {
		// Start typing your Java solution below
		// DO NOT write main() function
		if (s1 == null || s2 == null || s3 == null)
			return false;

		//		if (s1.isEmpty()) {
		//			if (s2.equals(s3))
		//				return true;
		//			else
		//				return false;
		//		}
		//		if (s2.isEmpty()) {
		//			if (s1.equals(s3))
		//				return true;
		//			else
		//				return false;
		//		}

		if (s1.length() + s2.length() != s3.length())
			return false;

		boolean match[][] = new boolean[s1.length() + 1][s2.length() + 1];
		match[0][0] = true;
		for (int i = 1; i < s2.length() + 1; i++) {
			if (match[0][i - 1] && s2.charAt(i - 1) == s3.charAt(i - 1))
				match[0][i] = true;
		}

		for (int i = 1; i < s1.length() + 1; i++) {
			if (match[i - 1][0] && s1.charAt(i - 1) == s3.charAt(i - 1))
				match[i][0] = true;
		}

		for (int i1 = 1; i1 < s1.length() + 1; i1++) {
			for (int i2 = 1; i2 < s2.length() + 1; i2++) {
				if ((match[i1 - 1][i2] && s1.charAt(i1 - 1) == s3.charAt(i1
						+ i2 - 1))
						|| (match[i1][i2 - 1] && s2.charAt(i2 - 1) == s3
								.charAt(i1 + i2 - 1)))
					match[i1][i2] = true;

			}
		}

		return match[s1.length()][s2.length()];
	}

	/**
	 * 
	 */
	public InterleavingString() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		InterleavingString is = new InterleavingString();
		String s1 = "a";
		String s2 = "b";
		String s3 = "ab";
		is.isInterleave(s1, s2, s3);
	}

}
